1. 题目

假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。编写一个算法来重建这个队列。

注意：总人数少于1100人

示例输入: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

2.1. 递归回溯

一开始是按先k升序，再h升序排序，先排[5,0]，再排[7,0]，排第三个人的时候有3种选择，只能想到递归回溯了。然后就超时了。。

所以应该有其他算法。这种太暴力了。看到这样一段话：

一般这种数对，还涉及排序的，根据第一个元素正向排序，根据第二个元素反向排序，或者根据第一个元素反向排序，根据第二个元素正向排序，往往能够简化解题过程。

2.2. 第一元素反向排序，第二元素正向排序

先按身高（k）从高到低排序，再按大于人数（h）从低到高排序

先排个高的，后面个矮的再怎么排，无论是排个高的前面还是后面，都不会影响到个高的h值。所以先按k降序排。那具体排哪儿呢，只需要排在第h+1个位置，使前面有h个不比他低的人就行。

如果身高相同，h大的人一定在h小的人后边。所以再按h升序排。

如此这般排完序后：[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] => [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

（下列计数从0开始计）

排第0个人[7,0] ：[ [7,0] ]

排第1个人[7,1]：[ [7,0], [7,1] ] 身高相同，h大的人排h小的人后边

排第2个人[6,1]：[ [7,0], [6,1], [7,1] ] 插入第1个位置，原来在第1个位置的[7,1]变成了第2个位置

排第3个人[5,0]：[ [5,0], [7,0], [6,1], [7,1] ] 插入第0个位置，原来后面的都后移1个位置

排第4个人[5,2]：[ [5,0], [7,0], [5,2], [6,1], [7,1] ] 插入第2个位置

排第5个人[4,4]：[ [5,0], [7,0], [5,2], [6,1], [4,4], [7,1] ] 插入第4个位置

3. 代码

3.1. 超时代码

class Solution {
public:
    const static int MAXN = 1100+5;
    int num,book[MAXN];
    bool flag = false;
    vector<vector<int>> ans;
    //已经排好了q-1位，将原队列第p个人排在新队列第q位是否满足条件
    bool isok(vector<vector<int>>& people, int p, int q){//O(n)
        int cnt = 0;//前q-1位人比第q位身高大于等于的人数
        for(int i=0;i<q;++i){
            if(ans[i][0]>=people[p][0]) cnt++;
        }
        return cnt==people[p][1];
    }
    void dfs(vector<vector<int>>& people, int k){//排第k个人
        if(k==num) {
            flag = true;
            return;
        }
        for(int i=0;i<num;++i){
            if(book[i]) continue;
            if(!isok(people, i, k)) continue;
            ans.push_back(people[i]);
            dfs(people,k+1);
            if(flag) return;
            ans.pop_back();
        }
    }
    bool static cmp(vector<int>& a, vector<int>& b){
        if(a[1]!=b[1]) return a[1]<b[1];
        else return a[0]<b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        num = people.size();//排队总人数
        sort(people.begin(),people.end(),cmp);
        dfs(people,0);
        return ans;
    }
};

3.2. 先排序再插入代码

class Solution {
public:
    bool static cmp(vector<int>& a, vector<int>& b){
        if(a[0]!=b[0]) return a[0]>b[0];
        else return a[1]<b[1];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        vector< vector<int> > res;
        for(auto& x: people){
            res.insert(res.begin()+x[1],x);
        }
        return res;
    }
};

sort函数部分 lambda函数简化编程：

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),[](const vector<int>& a, const vector<int>& b){
            if(a[0]!=b[0]) return a[0]>b[0];
            else return a[1]<b[1];
        });
        vector< vector<int> > res;
        for(auto& x: people){
            res.insert(res.begin()+x[1],x);
        }
        return res;
    }
};

406 根据身高重建队列